package com.base.dynamicprograming;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * @author leon
 * @date 2021年12月13日 15:08
 */
public class LongestPalindrome {
    /**
     * 动态规划:dp[i][j] = dp[i+1][j-1] 与运算 s[i] == s[j]
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;
        int begin = 0;
        // 只含有一个字符的，肯定是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 字符串的长度，从2到n
        for (int len = 2; len <= n; len++) {

            for (int i = 0; i < n; i++) {
                // 左端点是 i,右端点是j
                // j-i+1 = len
                int j = len+i-1;
                // 右端越界，推出循环
                if(j>=n){
                    break;
                }

                if(charArray[i] == charArray[j]){
                    if(len<3){
                        // 只有两个元素
                        dp[i][j] = true;
                    }else {
                        // 从前一个状态转移到当前状态
                        dp[i][j] = dp[i+1][j-1];
                    }
                }else {
                    dp[i][j] = false;
                }

                if(dp[i][j]&&len>maxLen){
                    maxLen = len;
                    begin = i;
                }
            }
        }

        return s.substring(begin,begin+maxLen);

    }



    public static void main(String[] args) {
        System.out.println(new LongestPalindrome().longestPalindrome("babad"));
    }
}
